// https://www.luogu.com.cn/problem/P3380
// https://soj.turingedu.cn/problem/60302/
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
using ll = long long;
const int inf = 2147483647;
#define rf(i, n) for (int i = 1; i <= (n); ++i)
int rad(); // read int
const int maxn = 5 + 5e4;
const int max_size = 5 + 1e7;

int n, q;
int a[maxn];
// splay===============================================================
int tsiz, tmpsiz;
struct Node {
    int val, siz;
} dat[max_size];
int tag[max_size];
int ch[max_size][2], fa[max_size];
inline int new_node(int v) {
    if (tmpsiz == 0) {
        dat[++tsiz] = {v, 1};
        return tsiz;
    }
    int ret = tmpsiz;
    tmpsiz = 0;
    fa[ret] = ch[ret][0] = ch[ret][1] = tag[ret] = 0;
    dat[ret] = {v, 1};
    return ret;
}
inline void pushup(int now) {
    dat[now].siz = dat[ch[now][0]].siz + dat[ch[now][1]].siz + 1;
}
inline void pushdown(int now) {
    if (tag[now]) {
        swap(ch[now][0], ch[now][1]);
        tag[ch[now][0]] ^= 1, tag[ch[now][1]] ^= 1;
        tag[now] = 0;
    }
}
void rotate(int now) {
    int father = fa[now], grand = fa[father], d = (now == ch[fa[now]][0]);
    ch[father][d ^ 1] = ch[now][d], fa[ch[now][d]] = father, pushup(father);
    ch[now][d] = father, fa[father] = now, pushup(now);
    fa[now] = grand;
    if (grand) ch[grand][father == ch[grand][1]] = now, pushup(grand);
    // if (grand) ch[grand][ch_type(father)] = now, pushup(grand); // fa[father] 已经被修改了，调用 ch_type 将导致错误
}
int splay(int now, int &root, int top = 0) {
    while (fa[now] != top) {
        int father = fa[now];
        if (fa[father] != top) rotate((now == ch[father][1]) ^ (father == ch[fa[father]][1]) ? now : father);
        rotate(now);
    }
    if (top == 0) root = now;
    return now;
}
void insert(int v, int &root) {
    int now = root, father = 0;
    while (now) {
        pushdown(now);
        father = now, now = ch[now][v > dat[now].val];
    }
    now = new_node(v), fa[now] = father;
    if (father) ch[father][v > dat[father].val] = now;
    splay(now, root);
}
int find(int v, int &root) {
    int now = root, father = 0;
    while (now) {
        pushdown(now);
        if (v == dat[now].val) return splay(now, root);
        father = now, now = ch[now][v > dat[now].val];
    }
    splay(father, root);
    return 0;
}
int erase(int v, int &root) { // 返回删除的节点的编号
    if (root == 0) return 0;
    if (find(v, root) == 0) return 0;
    if (ch[root][0] == 0 || ch[root][1] == 0) {
        int ret = root;
        root = ch[root][0] | ch[root][1], fa[root] = 0;
        return ret;
    }
    int d = (dat[ch[root][0]].siz > dat[ch[root][1]].siz); // 大的子树作新根，splay 以减高度
    int now = ch[root][d ^ 1];
    while (ch[now][d]) {
        pushdown(now);
        now = ch[now][d];
    }
    // splay(now, root);
    splay(now, root, root);
    fa[ch[root][d]] = now, ch[now][d] = ch[root][d], pushup(now);
    int ret = root;
    root = now, fa[root] = 0;
    return ret;
}
int get_rank(int v, int &root) { // return inf for no find
    int now = root, father = 0, lsiz = 0;
    while (now) {
        pushdown(now);
        if (v > dat[now].val) lsiz += dat[ch[now][0]].siz + 1;
        father = now, now = ch[now][v > dat[now].val];
    }
    splay(father, root);
    return lsiz;
}
int get_val(int rk, int &root) {
    int now = root, father = 0;
    while (now) {
        pushdown(now);
        int now_rk = dat[ch[now][0]].siz + 1;
        if (rk == now_rk) return dat[splay(now, root)].val; // find
        father = now, now = ch[now][rk > now_rk];
        if (rk > now_rk) rk -= now_rk;
    }
    splay(father, root);
    return 0;
}
int get_pre(int v, int &root) {
    int now = root, father = 0, back = -inf;
    while (now) {
        pushdown(now);
        if (v > dat[now].val) back = max(back, dat[now].val);
        father = now, now = ch[now][v > dat[now].val];
    }
    splay(father, root);
    return back;
}
int get_nex(int v, int &root) {
    int now = root, father = 0, back = inf;
    while (now) {
        pushdown(now);
        if (v < dat[now].val) back = min(back, dat[now].val);
        father = now, now = ch[now][v >= dat[now].val];
    }
    splay(father, root);
    return back;
}
void replace(int u, int v, int &root) {
    tmpsiz = erase(u, root);
    insert(v, root);
}
// void show(int now, int dep = 1) {
//     if (now == 0) return;
//     pushdown(now);
//     show(ch[now][0], dep + 1);
//     printf("%d ", dat[now].val - 1);
//     // printf("val: %d, siz: %d, dep = %d\n", dat[now].val, dat[now].siz, dep);
//     show(ch[now][1], dep + 1);
// }
// void reverse(int l, int r) {
//     int u = get_val(l - 1), v = get_val(r + 1);
//     splay(v), splay(u, v);
//     if (ch[u][1]) tag[ch[u][1]] ^= 1;
// }

// segtree=======================================================================
int segsiz, rot[maxn << 2];
// void init(int now, int l, int r) { // init the tree
//     if (l == r) {
//         tr[now] = {a[l], a[l], a[l], a[l]};
//         return;
//     }
//     int mid = l + r >> 1;
//     init(now << 1, l, mid);
//     init(now << 1 | 1, mid + 1, r);
//     tr[now] = merge(tr[now << 1], tr[now << 1 | 1]);
// }
void update(int now, int l, int r, int i, int x) {
    replace(a[i], x, rot[now]);
    if (l == r) {
        a[i] = x;
        return;
    }
    int mid = l + r >> 1;
    if (i <= mid)
        update(now << 1, l, mid, i, x);
    else
        update(now << 1 | 1, mid + 1, r, i, x);
}
int ask_rank(int now, int l, int r, int s, int t, int v) { // ask the [s, t]
    if (s <= l && r <= t) return get_rank(v, rot[now]);    // cover
    // push_down(now, l, r);
    int mid = l + r >> 1;
    if (t <= mid) return ask_rank(now << 1, l, mid, s, t, v);
    if (s > mid) return ask_rank(now << 1 | 1, mid + 1, r, s, t, v);
    return ask_rank(now << 1, l, mid, s, t, v) + ask_rank(now << 1 | 1, mid + 1, r, s, t, v);
}
int ask_pre(int now, int l, int r, int s, int t, int v) { // ask the [s, t]
    if (s <= l && r <= t) return get_pre(v, rot[now]);    // cover
    // push_down(now, l, r);
    int mid = l + r >> 1;
    if (t <= mid) return ask_pre(now << 1, l, mid, s, t, v);
    if (s > mid) return ask_pre(now << 1 | 1, mid + 1, r, s, t, v);
    return max(ask_pre(now << 1, l, mid, s, t, v), ask_pre(now << 1 | 1, mid + 1, r, s, t, v));
}
int ask_nex(int now, int l, int r, int s, int t, int v) { // ask the [s, t]
    if (s <= l && r <= t) return get_nex(v, rot[now]);    // cover
    // push_down(now, l, r);
    int mid = l + r >> 1;
    if (t <= mid) return ask_nex(now << 1, l, mid, s, t, v);
    if (s > mid) return ask_nex(now << 1 | 1, mid + 1, r, s, t, v);
    return min(ask_nex(now << 1, l, mid, s, t, v), ask_nex(now << 1 | 1, mid + 1, r, s, t, v));
}
int ask_val(int s, int t, int rk) { // ask the [s, t]
    int l = 0, r = 1e8 + 5;
    while (l < r) {
        int mid = l + r >> 1;
        // printf("%d %d\n", l, r);
        if (ask_rank(1, 1, n, s, t, mid) >= rk)
            r = mid;
        else
            l = mid + 1;
    }
    return r - 1;
}

// =================================================================================

int main() {
    memset(a, 0x3f3f3f3f, sizeof(a));
    n = rad(), q = rad();
    rf(i, n) {
        int tmp = rad();
        update(1, 1, n, i, tmp);
        a[i] = tmp;
    }
    while (q--) {
        int op = rad();
        if (op == 1) {
            int l = rad(), r = rad(), v = rad();
            printf("%d\n", ask_rank(1, 1, n, l, r, v) + 1);
            // printf("%d\n", get_rank(v, rot[1]));

        } else if (op == 2) {
            int l = rad(), r = rad(), rk = rad();
            printf("%d\n", ask_val(l, r, rk));
        } else if (op == 3) {
            int i = rad(), v = rad();
            update(1, 1, n, i, v);
        } else if (op == 4) {
            int l = rad(), r = rad(), v = rad();
            printf("%d\n", ask_pre(1, 1, n, l, r, v));
        } else if (op == 5) {
            int l = rad(), r = rad(), v = rad();
            printf("%d\n", ask_nex(1, 1, n, l, r, v));
        }
    }
}
int rad() {
    int back = 0, ch = 0, neg = 0;
    for (; ch < '0' || ch > '9'; ch = getchar())
        neg = ch == '-';
    for (; ch >= '0' && ch <= '9'; ch = getchar())
        back = (back << 1) + (back << 3) + (ch & 0xf);
    return (back ^ -neg) + neg;
}
/*
10 100
1 2 3 4 5 6 7 8 9 10
1 1 10 1
1 4 7 5

5 100
2 4 6 8 10

9 6
4 2 2 1 9 4 0 1 1
2 1 4 3



*/